00100			MACHINE VISUAL PERCEPTION
00200	
00300	In constructing systems which see, we gain in understanding human and
00400	machine  intelligence, by seeking answers to questions which arise in
00500	building a visual system: What are  useful  modules;  what  is  their
00600	conceptual   basis?   What  are  inherent  computational  limits,  in
00700	interconnections for  parallel  machines;  in  computation  time  for
00800	serial  machines?  What  conclusions can be drawn from the results of
00900	modules; how do these conclusions interact  with  other  conclusions?
01000	What is the system structure? How is knowledge represented? How is it
01100	integrated in the system? How does it guide  in  drawing  conclusions
01200	from  image  data? How does knowledge interact with conclusions drawn
01300	from the image? Given a system, what can it see?  What  is  necessary
01400	for visual learning? What are given systems capable of learning? Many
01500	results cannot be taken literally as models  for  biological  systems
01600	because  of  differences  in  hardware and gaps in our knowledge, but
01700	fundamental limitations are shared, and many examples are applicable.
01800	The research may occasionally borrow from biology, but we cannot copy
01900	nature,  since  the  details  are  not  known  and  the  hardware  is
02000	different.
02100	
02200	We   encounter   problems   which  are  widespread  in  intelligence.
02300	Visualization  is  an   important   part   of   problem-solving   and
02400	mathematics.  Graphs  and  visual  displays  are an important part of
02500	communication.  Representation  of   knowledge   and   its   use   in
02600	goal-directed  ways  are  universal  problems in intelligence. Visual
02700	representations  have  important  applications  productivity  and  to
02800	augment  man-machine  communication.  Computer  graphics  and  design
02900	automation are already  useful  in  industry.  With  designs  in  the
03000	computer,  it  has  the  knowledge  to  aid  in controlling parts and
03100	material flow, designing transport systems, extending modularity  and
03200	commonality  of  parts  and  procedures over a wider production base,
03300	sensing and monitoring production, and increasing  communication  and
03400	the  ability  to  analyze  industrial processes. These abilities will
03500	have a profound effect on near term productivity. They depend on  the
03600	ability to describe objects and processes in ways which express shape
03700	adequately. They require techniques  from  across  the  AI  spectrum,
03800	including the most advanced.
03900	
04000	Industry   uses   hundreds   of   industrial  robots,  some  computer
04100	controlled. Touch and simple vision can incrementally  improve  these
04200	robots  which  now have no sensing and no contingency actions. Visual
04300	problems can be simplified by design choices, such as  color  coding.
04400	Visual  feedback is a useful problem for AI research in goal-directed
04500	systems. Programming robots must be made simple and rapid. Setting up
04600	a  new  assembly  task  is  an  occasional job which can be done on a
04700	time-sharing computer with advanced languages and  the  whole  of  AI
04800	techniques.
04900	
05000	
05100			Define the Field
05200	
05300	We  are interested in visual systems for function of an organism such
05400	as a robot. It must manipulate or avoid objects,  not  just  classify
05500	them.  Thus  it  needs  three-dimensional interpretations and spatial
05600	relations of objects. Certain techniques  have  evolved  for  simpler
05700	problems;  e.g.  template matching or vector space classification for
05800	character recognition. It seems attractive to simply save  images  or
05900	feature  vectors,  then match against a scene or part of a scene. But
06000	objects occlude one another, parts have joints which move separately,
06100	there  are  many viewpoints, many possible objects, many combinations
06200	of objects, classes are not identical with shape,  spatial  relations
06300	involve  complex deductions from the image, and we must deal with new
06400	objects. Such techniques are impractical for these conditions and are
06500	useful only in limited ways here.
     

00100		ELEMENTS OF A VISUAL SYSTEM
00200	
00300	The computer eye is some form of tv camera with color filters and a
00400	turret or zoom lens for closeup views.  The computer controls filters,
00500	lens and other parameters to optimize the image for each task [Tenenbaum].
00600	Sensor systems have inadequate dynamic range but system design studies
00700	suggest better compromises [Binford].  Humans use depth information
00800	obtained from stereo and motion parallax.  Several depth sensors
00900	based on triangulation have been built [Agin, Shirai, Munson].
01000	Range information with color should greatly simplify interpretation of
01100	scenes.
01200	
01300	The image is read into memory as an array of brightness values 
01400	(typically 300x300) with 4-8 bits for each sample for each color.
01500	The process of interpreting this mass of numbers into a symbolic
01600	description can be thought of as subdivided into segmentation,
01700	representation, and interpretation.
01800	
01900	The process of segmentation of a scene partitions it into meaningful entities
02000	which may be recognizable.  Segmentation in character recognition
02100	is simple since printed characters are clearly separated and
02200	labelled by black on white.
02300	It is harder to segment objects in a real scene (even simple scenes)
02400	because there are many possible properties for segmentation:
02500	uniformity of brightness, color, texture (itself a complex descriptor),
02600	regularity of boundaries, contiguity of depth (given stereo or other
02700	depth measurements).  Segmentation may also depend on depth cues from
02800	interpretation of texture gradients and occlusion.
02900	
03000	In what form do we represent objects internally in the computer?  The
03100	simplest form is a pictorial template, an array of brightness values
03200	to be matched directly against fragments of scenes by correlation.
03300	Given the inadequacies of this representation, we must describe
03400	partitioned regions symbolically in terms of extracted features like
03500	color, size, texture, and shape.  All these properties are inferred
03600	by complex processes from the image.  Simple descriptors for shape or
03700	texture may be used in simple tasks and limited context.  Shape might
03800	be described by the  ratio of the squared perimeter to the area of
03900	a region.  More sophisticated shape representations, needed for a wider
04000	range of tasks, are described later.
04100	
04200	Interpretation is often expressed as computing a distance measure between an
04300	object and a stored model.  For simple cases that can be useful.  When
04400	objects are occluded, there must be a partial match.  When objects are
04500	not identical, judgments of similarity depend on representation of
04600	shape and representation of the task, in order to define important
04700	differences.  The most useful approach is to build up symbolic
04800	descriptions and make symbolic descriptions of differences.  Sometimes,
04900	there are few enough models that matching with each model is possible.
05000	More generally, interpretation must make use of a large visual memory.
05100	
05200	Because of the evident interconnection of these three processes, one
05300	cannot proceed sequentially through segmentation, representation and interpretation
05400	and expect to obtain a globally consistent interpretation for all objects
05500	in a scene.  
     

00100			BLOCKS WORLD
00200	
00300	Research concentrated initially on scenes  of  blocks  as  a  simpler
00400	subproblem.  Roberts important work opened the field []. Objects were
00500	represented as built up of primitive parts, a block, a wedge,  and  a
00600	hexagonal  prism.   Primitives  were represented by their vertices in
00700	three dimensions. The program assumed it would first  obtain  perfect
00800	line  drawings.   It  attempted to identify unobscured polygons, then
00900	match sets of vertices to topologically  equivalent  model  vertices.
01000	Recognition  meant  finding  a three-dimensional model which could be
01100	translated, rotated, and scaled, then projected to match part of  the
01200	image.   The  recognized  piece  was  then cut away and the remainder
01300	considered. Some segmentation was performed with the recognition.
01400	
01500	That organization has proven inadequate. It  is  not  enough  to  use
01600	models  and template matching. Producing perfect line drawings is not
01700	practical. Some lines are missed. Shadows,  reflections  and  surface
01800	markings  cause  extra lines. Errors made at one stage are compounded
01900	by later stages.
02000	
02100	Guzman found  heuristics  to  segment  complex  scenes  into  objects
02200	without  template  matching.   The program linked regions at vertices
02300	with three lines if they  were  not  a  T,  between  regions  without
02400	concavities  (internal  angle less than pi) at the vertex. See figure
02500	1a. Eventually he required almost the same condition at both ends  of
02600	a  line  before  linking  (except that T was allowed at one end). See
02700	figure 1b. We have rephrased his  conditions  for  clarity.   Regions
02800	linked  twice  were  joined  into clusters; regions linked twice to a
02900	cluster were also joined. Other links were  introduced  without  much
03000	motivation.  The program did surprisingly well, but had problems with
03100	holes and other non-convexities, and with accidental  alignment.   It
03200	depended  on  being  told  the  background.  These techniques did not
03300	extend far. Falk joined lines into edges  of  bodies;  since  missing
03400	edges cause regions to be non-planar, some errors could be avoided.
03500	
03600	Huffman   and   Clowes  []  analyzed  trihedral  vertices  seen  from
03700	non-singular perspective (small change of viewpoint leaves the number
03800	of  visible  lines unchanged) by classifying edges as convex, concave
03900	and obscuring. It was possible to reject some drawings as  impossible
04000	under  these  assumptions.  Waltz expanded that labelling of lines to
04100	include cracks, shadows, and illumination. It would  seem  that  such
04200	large  numbers  of  possible  interpretations  would  be unmanagable;
04300	instead,  the  increased  precision  of  descriptions  allows   rapid
04400	discarding of wrong interpretations. Not only are solutions possible,
04500	they are quickly obtained. In considering possible solutions,
04600	
04700	
04800	
04900	
05000	
05100	The best performance  in  segmenting  image  data  is  given  by  the
05200	Binford-Horn  []  line finder and the Shirai [] line finder.  The two
05300	are complementary and should be combined.  The former is able to find
05400	most  lines  in  a  scene  of  white  blocks on a white background in
05500	arbitrary lighting.  It  misses  a  few  lines  which  are  found  by
05600	subsequent  prediction  and  verification  and garbles some vertices.
05700	Shirai's system performs much better.   It  requires  large  contrast
05800	with background however (white on black), and finds only features and
05900	objects for which cues are available from context.
06000	
06100	It is interesting  to  compare  these  systems  with  the  biological
06200	system.  Directional  edge  operators  are  scanned  over  the  image
06300	[Binford, Hueckel]; these compare  with  the  Hubel-Wiesel  cells  in
06400	higher  animals.   In  practice,  large  gradients at reflections and
06500	curved surfaces cause masses of spurious edge fragments.  These  were
06600	eliminated  by  subtracting  the  local  average  at each point, thus
06700	subtracting out smooth gradients [Binford].  This process is familiar
06800	as lateral inhibition in the retina of animals.
06900	
07000	The  Binford-Horn  program  used an optimal curve sequential decision
07100	process to extend curves and test at each extension, whether to keep,
07200	terminate,  or  extend further.  Shirai began with white objects on a
07300	black background; context was used at each step to decide what to  do
07400	next.   At  vertices,  the  extension  of  boundary lines was tested.
07500	Completions for unterminated  lines  was  searched  for.   Additional
07600	lines  were  tested for at vertices, including some parallel to lines
07700	at adjacent vertices.  The  use  of  context  involved  not  changing
07800	thresholds,  but  using  special-purpose  operators: verify a line at
07900	known position and angle; find a line through a vertex.
08000	
     

00100			REAL WORLD VISION
00200	
00300	
00400	
00500	The blocks world illustrates many basic aspects of machine perception,
00600	but many other critical problems encountered in perceiving real world
00700	scenes do not arise.  Important problems in segmentation were avoided
00800	by using uniformly painted blocks.  Segmentation of boundaries was
00900	specialized to straight lines.  Region-growing  and edge-finding
01000	techniques require generalizations to regions of uniform texture.
01100	
01200	In some cases we are interested in representing gross characteristics
01300	of shape, texture and other features, eg for description of trees.
01400	In other cases, we are interested in more complex descriptions than
01500	characterized polyhedra, as in descriptions of machined parts or people.
01600	
01700	It is not conceivable in real world scenes to search through a complete
01800	set of known prototypes seeking interpretations.  The system must limit
01900	interpretations to those familiar in the context, and use brief descriptions
02000	to select a small subset of possible object interpretations.
02100	
02200	The same information overload affects segmentation and the interconnection
02300	of segmentation with interpretation.  The overload is not to be solved
02400	by merely building faster computers and bigger memories; hardware
02500	improvements will aid adequate techniques but do little for exhaustive
02600	techniques.
02700	
02800	Description of simple polyhedral scenes was difficult enough;
02900	with these added obstacles, is there hope for success in perceiving the
03000	real world?
03100	The full problem is broader, in some places deeper, but in many places
03200	shallower.  For blocks, we restricted our programs to black and white images
03300	and distinguished structures of blocks solely on the basis of shape.
03400	In the real world, we use color, texture, depth, size (which is not
03500	very relevant for blocks), and surface orientation.  Our goal is not
03600	complete descriptions; for a given task, the system need be concerned
03700	with only a few objects necessary for its goals.  Shapes of complex objects,
03800	while they may be difficult to describe, often discriminate very simply
03900	from other objects of interest.  Real world objects are found in
04000	well-defined contexts; eg telephones are attached to cords.
     

00100			REAL WORLD VISION
00200	
00300	Studies for agricultural and earth resources surveys have  considered
00400	texture as a two-dimensional problem.  Bajcsy [] has analyzed outdoor
00500	scenes for which perspective and  three-dimensional  description  are
00600	important.   Textures were described by structures of texture elements with spatial
00700	relations.  Descriptors  for  texture  elements  and  relations  were
00800	obtained  from  the  Fourier  transform  for directionality (if any),
00900	size, contrast, and spacing of texture elements. The Fourier  transform
01000	was   found troublesome,however.   Color  and  texture  regions  were
01100	obtained.  Some  depth  relations  could  be  observed  from  texture
01200	gradient.   An  attempt was made to obtain consistent interpretations
01300	by first confirming  region  boundaries  by  independent  properties,
01400	making  three-dimensional  interpretations, and matching region descriptors with
01500	those of sky, trees, grass, etc. in a world model.
01600	
01700	quality of interpretation was limited by unreliability of region-growing process.
01800	Further work in outdoor  scenes attempts to  incorporate  the  world  model  and
01900	interpretation into the region growing process.
02000	  An interpretation of
02100	image regions  as  sky,  trees,  etc.  is  evaluated  by  calculating
02200	probabilities  for  consistency  of  object descriptions and boundary
02300	description.    Consistent   interpretations   which   maximize   the
02400	probabilistic evaluation are sought.
02500	
02600	Regions are merged  not only because of similarity of properties, but
02700	because
02800	the consistency of semantic interpretation 
02900	is improved.
     

00100		Representation
00200	
00300	
00400	We do not think a single representation is adequate throughout a system,
00450	but we have attempted to analyze tasks in terms of computational primitives
00475	required for
00500	descriptions of shape which are adequate for typical robot tasks
00600	such as manipulation, collision avoidance, display, and recognition.
00700	Although many would disagree with our criteria, the design criteria
00800	were:[]
00900	a) Representations should be symbolic at a high level in order
01000	to interface with knowledge of the problem domain.
01100	b) Representations should depend on segmentation into parts,
01200	which may have subparts.
01300	c) Primitives should be three-dimensional volume descriptions,
01350		rather than surface descriptions.
01500	d) Descriptions should be generative.  A modest collection of
01600	primitives should allow description of a vast set of objects.
01700	
01800	Figures show experimental results of computer descrition of some
01900	objects [Agin].  They give some indication of the primitives of the
02000	representations, and their power, even with preliminary programs.
02100	The representations [Binford 1971] depend upon segmentation to
02200	describe complex objects in terms of parts.  The representations
02300	are grqph-structured. Parts are structures of the same form.
02350	The description of a man is shown below.
02355			       [HEAD]
02359				 |
02363				NECK
02367				 |
02371		      [ARM]--<SHOULDERS>--[ARM]
02375				 |
02379			       TRUNK
02383				 |
02387			      <HIPS>
02391			      |    |
02395			  [LEG]    [LEG]
02400	The utility of these representations lies in defining primitives
02500	which allow a natural choice of parts.  Parts are joined by "pasting";
02600	holes are made by "cutting". 
02650	
02675	Primitive parts are described by
02700	"generalized local translational invariance", a formal construction
02750	which generates 
02775	solids by transforming and translating an arbitrary cross section
02780	along a space curve (the axis).  If the transformation scales the
02785	cross section, then the solid generated is locally conical.  The
02790	representation is thus specified by an axis which is a space curve,
02795	and an arbitrary normal cross section along the axis.  Snake-like
02800	objects, helices, toroids, and locally helical and toroidal shapes are
02805	naturally described.